package com.sheng.leetcode.year2022.month05.day31;

import org.junit.Test;

import java.util.*;

/**
 * @author liusheng
 * @date 2022/05/31
 *
 * 剑指 Offer II 114. 外星文字典
 *
 * 现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。
 * 给定一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
 * 请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序 排列。
 * 若不存在合法字母顺序，返回 "" 。若存在多种可能的合法字母顺序，返回其中 任意一种 顺序即可。
 * 字符串 s 字典顺序小于 字符串 t 有两种情况：
 * 在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
 * 如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。
 *  
 * 示例 1：
 *
 * 输入：words = ["wrt","wrf","er","ett","rftt"]
 * 输出："wertf"
 * 示例 2：
 *
 * 输入：words = ["z","x"]
 * 输出："zx"
 * 示例 3：
 *
 * 输入：words = ["z","x","z"]
 * 输出：""
 * 解释：不存在合法字母顺序，因此返回 "" 。
 *
 * 提示：
 *
 * 1 <= words.length <= 100
 * 1 <= words[i].length <= 100
 * words[i] 仅由小写英文字母组成
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/Jf1JuT
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCodeAlienOrder {

    @Test
    public void test01(){
        String[] words = {"wrt","wrf","er","ett","rftt"};
        System.out.println(new Solution().alienOrder(words));
    }

}
class Solution {

    //VISITING值代表不正常，VISITED代表正常
    static final int VISITING = 1, VISITED = 2;
    //edges：以字符串数组中的某个字母为key，值为顺序在该字母之后的所有字母的集合
    Map<Character, List<Character>> edges = new HashMap<Character, List<Character>>();
    //states：以字符串数组中的某个字母为key，值为VISITING或者VISITED，全部为VISITED则代表字符串数组顺序全部正常
    Map<Character, Integer> states = new HashMap<Character, Integer>();
    //true则代表字符串顺序正常，false则代表不正常
    boolean valid = true;
    //字母按照顺序存放于order数组中
    char[] order;
    //order数组的索引，从最后一位开始，逐次减一
    int index;

//    public String alienOrder(String[] words) {
//        //如果首字母相等，则继续往后一个字符比较，直到其中一个字符串结束或者出现不相等的字符为止
//        for (int i = 1; i < words.length; i++) {
//            String str1 = words[i - 1], str2 = words[i];
//            int i1 = 0, i2 = 0;
//            List<String> list = new ArrayList<>();
//            while (i1 < str1.length() && i2 < str2.length()) {
//                //两字母相等
//                if (str1.charAt(i1) == str2.charAt(i2)) {
//                    i1++;
//                    i2++;
//                    continue;
//                }
//                //不相等
//                list.add(str1.charAt())
//            }
//        }
//        return null;
//    }

    public String alienOrder(String[] words) {
        //获取字符串列表的长度
        int length = words.length;
        //循环字符串数组
        for (String word : words) {
            //获取字符串数组中每个字符串的长度
            int wordLength = word.length();
            //循环字符串中的每一个字母
            for (int j = 0; j < wordLength; j++) {
                char c = word.charAt(j);
                //将字符存到edges集合中（putIfAbsent：判断key是否存在，不存在则插入）
                edges.putIfAbsent(c, new ArrayList<Character>());
            }
        }
        //循环判断前后两个字符串之间的字母顺序
        for (int i = 1; i < length && valid; i++) {
            addEdge(words[i - 1], words[i]);
        }
        //初始化一个长度和edges集合元素数量一致的char[]，即字符串数组出现的所有的字母的数量
        order = new char[edges.size()];
        //index代表数组长度减一，0  ~  length-1
        index = edges.size() - 1;
        //将集合edges的key拿出来作为一个Set集合
        Set<Character> letterSet = edges.keySet();
        //循环Set集合
        for (char u : letterSet) {
            //如果当前字母不存在于states集合中时，执行dfs方法
            if (!states.containsKey(u)) {
                dfs(u);
            }
        }
        //valid为false代表字符串顺序错误
        if (!valid) {
            return "";
        }
        //将char数组转换为字符串返回
        return new String(order);
    }

    //前后字符串之间的比较
    public void addEdge(String before, String after) {
        int length1 = before.length(), length2 = after.length();
        int length = Math.min(length1, length2);
        int index = 0;
        while (index < length) {
            //如果两个字母相等则比较下一个字母
            char c1 = before.charAt(index), c2 = after.charAt(index);
            if (c1 != c2) {
                //不相等，将后一个字母拼接在后面，然后跳出循环
                edges.get(c1).add(c2);
                break;
            }
            index++;
        }
        //如果此时index == length，代表，两个字符串相同字母的数量一致，需要判断，字符串长度，避免abc， ab这种情况出现
        if (index == length && length1 > length2) {
            valid = false;
        }
    }

    //参数u代表首字母
    public void dfs(char u) {
        states.put(u, VISITING);
        //adjacent：字母u后面跟着的所有元素的集合
        List<Character> adjacent = edges.get(u);
        //循环集合
        for (char v : adjacent) {
            //如果当前字母不存在于states集合中，则继续迭代
            if (!states.containsKey(v)) {
                dfs(v);
                //valid为false代表字符串顺序错误
                if (!valid) {
                    //返回当前方法，导致在states集合中以改字母为key的value值为VISITING
                    return;
                }
            //当前字母存在于states集合中，代表当前字母已经dfs执行过了，同时如果value值为VISITING，代表在迭代过程中字符串顺序错误
            } else if (states.get(v) == VISITING) {
                valid = false;
                return;
            }
        }
        //已该字母和该字母后面跟着的字母的迭代都没有出问题，走到这一步，将value值设置为VISITED，代表正常
        states.put(u, VISITED);
        //dfs深度优先遍历，最开始走的这里的是排在最后面的字母
        order[index] = u;
        //将索引减一
        index--;
    }
}

////idx用来记录边的索引，cnt用来比对出现的字母数量，如果图建完之后是一个有向无环图，拓扑排序一定能完成，数量肯定跟题目中出现的字母数量一致
//    int idx = 0,cnt=0;
//    //he是用来存储顶点的
//    //e是用来存储这条边的尾结点的
//    //ne是用来存储这条边属于哪个顶点的
//    int[] he=new int[26],e=new int[26*26],ne=new int[26*26];
//    //拓扑排序，还需要出度和入度
//    int[] in=new int[26],out=new int[26];
//    //是否有这个字母所表示的顶点
//    boolean[] isVisited=new boolean[26];
//    //建图方法
//    void add(int a,int b){
//        e[idx]=b;
//        ne[idx]=he[a];
//        he[a]=idx;
//        idx++;
//        in[b]++;
//        out[a]++;
//    }
//    public String alienOrder(String[] words) {
//        int n = words.length;
//        Arrays.fill(he,-1);
//        for (int i = 0; i < n; i++) {
//            for(char c:words[i].toCharArray()){
//                //如果有这个顶点，比如26个字母可能图中只有5个字母的话，我们只需要操作这5个字母
//                if (!isVisited[c-'a']&&++cnt>0) isVisited[c-'a']=true;
//            }
//            for (int j = 0; j < i; j++) {
//                if (!build(words[j],words[i] )) return "";
//            }
//        }
//        //开始遍历
//        Deque<Integer> queue = new ArrayDeque<Integer>();
//        for (int i = 0; i < 26; i++) {
//            //拓扑排序，每次寻找入度为0的点开始遍历
//            if (isVisited[i]&&in[i]==0) {
//                //是有可能存在好几个入度为0的点的，这个时候先删除里面哪个都ok
//                queue.addLast(i);
//            }
//        }
//        StringBuilder sb = new StringBuilder();
//        while (!queue.isEmpty()) {
//            int u=queue.pollFirst();
//            sb.append((char)(u+'a'));
//            //遍历这个顶点的所有边
//            for (int i = he[u]; i !=-1 ; i=ne[i]) {
//                int j=e[i];
//                if (--in[j]==0) queue.addLast(j);
//            }
//        }
//        return sb.toString().length()==cnt? sb.toString():"";
//    }
//    private boolean build(String a,String b){
//        int m=a.length(),n=b.length();
//        int len=Math.min(m,n);
//        for (int i = 0; i < len; i++) {
//            int c1=a.charAt(i)-'a',c2=b.charAt(i)-'a';
//            //每次传进来两个字符串只会有两个顶点完成了建图
//            if (c1!=c2){
//                add(c1,c2);
//                return true;
//            }
//        }
//        //题目中说 如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。
//        return m<=n;
//    }

//class Solution {
//    static final int VISITING = 1, VISITED = 2;
//    Map<Character, List<Character>> edges = new HashMap<Character, List<Character>>();
//    Map<Character, Integer> states = new HashMap<Character, Integer>();
//    boolean valid = true;
//    char[] order;
//    int index;
//
//    public String alienOrder(String[] words) {
//        int length = words.length;
//        for (String word : words) {
//            int wordLength = word.length();
//            for (int j = 0; j < wordLength; j++) {
//                char c = word.charAt(j);
//                edges.putIfAbsent(c, new ArrayList<Character>());
//            }
//        }
//        for (int i = 1; i < length && valid; i++) {
//            addEdge(words[i - 1], words[i]);
//        }
//        order = new char[edges.size()];
//        index = edges.size() - 1;
//        Set<Character> letterSet = edges.keySet();
//        for (char u : letterSet) {
//            if (!states.containsKey(u)) {
//                dfs(u);
//            }
//        }
//        if (!valid) {
//            return "";
//        }
//        return new String(order);
//    }
//
//    public void addEdge(String before, String after) {
//        int length1 = before.length(), length2 = after.length();
//        int length = Math.min(length1, length2);
//        int index = 0;
//        while (index < length) {
//            char c1 = before.charAt(index), c2 = after.charAt(index);
//            if (c1 != c2) {
//                edges.get(c1).add(c2);
//                break;
//            }
//            index++;
//        }
//        if (index == length && length1 > length2) {
//            valid = false;
//        }
//    }
//
//    public void dfs(char u) {
//        states.put(u, VISITING);
//        List<Character> adjacent = edges.get(u);
//        for (char v : adjacent) {
//            if (!states.containsKey(v)) {
//                dfs(v);
//                if (!valid) {
//                    return;
//                }
//            } else if (states.get(v) == VISITING) {
//                valid = false;
//                return;
//            }
//        }
//        states.put(u, VISITED);
//        order[index] = u;
//        index--;
//    }
//}
//
//作者：LeetCode-Solution
//链接：https://leetcode.cn/problems/Jf1JuT/solution/wai-xing-wen-zi-dian-by-leetcode-solutio-to66/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
